НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №3 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «МЕТОДИ СОРТУВАННЯ» Варіант № 16 Дата «02» травень 2022  Київ 2022 Мета роботи: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування Завдання до лабораторної роботи: Розробити програму з алгоритмом згідно варіанту з використанням методів сортування. Оцінити час виконання та складність алгоритм. Варіанти індивідуальних завдань 1. Провести сортування масивів вказаним методом та у вказаному порядку. Для тестування алгоритмів сортування масив (10x10, та більше бажанням). 2. Самостійно обрати додатковий метод та провести сортування того ж масиву. 3.Порівняти кількість перестановок (або час виконання) обох методів. Спробувати порівняти час виконання сортування з масивом більшого розміру, який створити за допомогою генератора випадкових чисел. Завдання: Метод сортування вставками для 16 варіанту. / рис 1. Теоретичні відомості: What is the Quick Sort Program in C? The main process in a quicksort algorithm is partitioning. If x is the pivot in an array, then the main intent of the sorting process is to put x at the right position in a sorted array, such that smaller elements precede x and greater elements follow it. Once the pivot element has been selected, the elements smaller than the pivot element are placed before it, and the greater ones after. There are several variations of the quick sort algorithm, depending on what kind of element (or number) is selected as the pivot: The first element as the pivot The last element as the pivot A random element as the pivot Median as the pivot Метод сортування вставками. Головна ідея метода є у тому, що при додавання нового елементу до вже отсортуваного масиву його треба вставити на потрібне міце, замість того щоб ставити його у довільне, і потім заново сортирувати усю послідовність. сортування вставками має велику вичіслювальну складність. Тому вона ефективна на невеликих наборах даних. Рекомендується використовувати цей метод на наборах до десятків елементів. сортування вставками ефективна на послідовностях з даними, які вже частково відсортовані. Хід роботи: Написано програмний код, який виконує завдання різними способами на вибір, або за допомогою метода сортивування вставками або методом швидкого сортування. Для цього було створено два метода. Було проведено оцінку часової складності алгоритму та порівняно час роботи та кількість ітерацій з різною для різної кількості елемнтів матриці(10, 50, 100, 500). Оцінку часу роботи наведено нижче у вигляді таблиці та графіку. Було створенно метод для полегшення метода main, у якому відбувалося наповнення матриці випадковими числами(getMatrix). цей метод можна спростити до 2n^2+9n+4 = Θ(n^2). Метод InsertionSort має цикл в циклі тому перший цикл буде 4+2n, потім йде 3 ітерації в циклі це 3n, Далі цикл у циклі з двома ітерації перевірки кожен раз і ще дві ітераціїї тому це можна звести до 4n^2. Загалом звести метод можна до 4+2n+3n+4n^2=4n^2+5n+4 = Θ(n^2). Метод quickSort має в найгіршому випадку для вхідного масиву з n елементів час роботи, дорівнює Θ(n 2 ). Дивлячись на таку повільну роботу в найгіршому випадку, цей алгоритм на практиці часто є оптимальним через те, що у середньому час його роботи набагато краще: Θ(n lg n) Підрахуємо ітерації: Ми маємо два цикли які виконуються n/2 раз, в кожному циклі по одній ітерації, тому можна сказати що вони разом буть 4*n/2=2n; Оскільки цей метод є рекурсивним, далі є формування рекурсії: в найгыршому випадку ми будемо перевіряти n разів, тому можна звести до 2n*n. Загалом метод можна звести до 2n^2+2n= Θ(n^2).(як і було сказано вище) Загалом завдання має такі ітераці: Цикл for тобто 4+2n ітерацій у ньому одна ітерація(виділення пам’яті для динамічного масиву); потім ще один цикл тому це буде...